package tree;

public class ConstructBinaryTreeFromPreorderAndInorderTraversal105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length < 1 || inorder.length < 1) {
            return new TreeNode();
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }


    private TreeNode buildTree(int[] pre, int pre_begin, int pre_end, int[] in, int in_begin, int in_end) {
        if (pre_begin > pre_end) {
            return null;
        }

        if (in_begin > in_end) {
            return null;
        }
        TreeNode root = new TreeNode(pre[pre_begin]);
        int index = in_begin;
        for (int i = in_begin; i < in_end + 1; i++) {
            if (in[i] == root.val) {
                index = i;
                break;
            }
        }
        root.left = buildTree(pre, pre_begin + 1, pre_begin + (index - in_begin),
                in, in_begin, index - 1);
        root.right = buildTree(pre, pre_begin + (index - in_begin) + 1, pre_end,
                in, index + 1, in_end);

        return root;

    }


}
